1. Field of the Invention
The present invention relates to a packet exchange and a router, and more particularly it relates to a packet exchange and a router and an input packet processing method thereof characterized by the processing such as supplying a packet received from a line, to the switch through the line cards, in a packet exchange formed by a plurality of line cards and a switch.
2. Description of the Related Art
With the spread of Internet, there arises such a problem that traffic on an IP (Internet protocol) network is so much increased that the conventional IP router is difficult to carry data efficiently and to maintain the quality of service. As a communication method in order to solve this problem, there is an MPLS (Multi Protocol Label Switching) method.
The technique of the MPLS method is described in, for example, IEEE COMMUNICATIONS MAGAZINE, VOL. 37, NO. 12, DECEMBER, 1999, pp. 36-68.
In the MPLS, an IP packet having the format as shown in FIG. 3(A) is encapsulated by the data called a shim header as shown in FIG. 3(B). Within a shim header, there exists a label that is an identifier indicating the routing information as shown in FIG. 3(C). Provided with a 20-bit long field, this label can distinguish 1,000,000 incoming packets. An MPLS packet can adopt a hierarchical structure with a plurality of shim headers attached as shown in FIG. 3(D), which is called label stacking. An LSR (Label Switch Router) performs routing and switching processing on an MPLS packet having arrived there based on the label and transfers the packet to an adjacent router.
Further, the packet is encapsulated by a PPP packet defined by, for example, RFC 1661 of IETF and transferred to and from a line. The PPP can carry an IP packet and an MPLS packet, and upon receipt of the PPP packet, the LSR judges whether the received packet is an IP packet or an MPLS packet. A control signal for setting label information on the LSR is served by using an LDP (Label Distribution Protocol) which employs a TCP on an IP packet not on an MPLS packet as a transport layer.
There are three kinds of LSRs, respectively called Ingress Edge-LSR, Core LSR, and Egress Edge-LSR. The Ingress Edge-LSR classifies IP packets received from a line into specified combinations based on each source address and destination address within IP headers. This is referred to as classification into FEC (Forwarding Equivalence Class). The Ingress Edge-LSR determines whether MPLS should be performed on the IP packet group classified into this FEC or not, and if necessary, it changes the same into MPLS packets and transfers them to an adjacent LSR. The Core LSR relays the MPLS packets. At the relay, the Core LSR performs the processing such as swapping the label of an incoming packet with the label for outgoing (referred to as a Swap, and only the label within a shim header is swapped), adding a new shim header to a packet (referred to as a Push), and removing a leading shim header (it may be a plurality of shim headers) from a packet (referred to as a Pop), and transfers the processed packets to an adjacent LSR. The Egress Edge-LSR removes each label from the top of the incoming packets, changes them into the IP packets, and transfers the same packets to an adjacent IP router by the IP routing.
In the MPLS packet processing procedure by the LSR, when an MPLS packet arrives at a line input interface, the LSR refers to a table called ILM (Incoming Label Map), with a label within the shim header of the incoming packet used as a key. The ILM includes pointers, indicating a table describing which kind of label operation should be performed on some input label, which is called NHLFE (Next Hop Label Forwarding Entry). The routing processing is performed based on the NHLFE. Thereafter, the LSR performs switching processing therein and sends the packets from a line output interface to an adjacent LSR and IP router. The Ingress Edge-LSR pushes a label on a packet requiring the MPLS, of the IP packet group classified into the FEC, after referring to the NHLFE. Although the operation by use of the ILM and the NHLFE is defined in the IETF draft specification (where the architecture of the MPLS is defined), the installation thereof is not defined.
As the existing installation method of an exchange or a router, there is a method of forming an exchange or a router with a plurality of line cards and a switch card. Generally, a line card can be provided with a plurality of lines, and the communication band of one line card is predetermined in advance. For example, in the case of the band of 2.4 Gbps (Giba Bit Per Sec), a line of the transfer rate 2.4 Gbps could hold one line and a line of the transfer rate 155 Mbps (Mega Bit Per Sec) could hold 16 lines. Here, the MPLS can hold a label space per each line. Therefore, the same label value may be used in different lines. If an identifier bit for discriminating each input line is added to the 20-bit label on the line cards in order to identify a label for each line, 24 bits becomes necessary as a reference key of the ILM when one line card holds 16 lines. Then, it becomes possible to discriminate 16,000,000 incoming packets.
On the other hand, in a design of a system, it is difficult to use as many as 16,000,000 identifiers at once for the reason of restriction of a memory and complication of management, and the number of the identifiers of the incoming packets to be used is restricted. In the MPLS, this is realized by restricting the number of the pointers indicated by the ILM to the number usable by a system.
Assuming that the number of the identifiers usable by one line card is 64,000, the pointer belonging to each entry of the ILM is two bites (16 bits). In order to provide a system with the ILM having the above 24 bits as an address for gaining access to a memory, the memory amount of 32 Mega bites is necessary. However, since the area actually used is 128 kilo bites (64,000×2 bites), almost all the areas of a memory become useless.
The conventional technique for discriminating input labels as the above is disclosed in Japanese Patent Laid-Open No. 8-510102, “Label Processing within Packet Network”. In this technique, assuming that an input label is formed by a first portion and a second portion being fixed previously, an exchange can perform the identification processing on the incoming packets in the three modes of: (1) the labels of the first portion and the second portion, (2) only the label of the first portion, and (3) only the label of the second portion. This technique, however, has no consideration of the input line number. When an input label of the above mode (2) corresponding to the MPLS is formed by only the first portion, the input label is used as an address for memory access in searching a table corresponding to the first portion. In this method, however, when the bit length of the first portion is long like the MPLS label, there is a problem such as requiring a large amount of memory as mentioned above, and an efficient use of a memory is impossible.
On the other hand, as the result of referring to the ILM and NHLFE, the MPLS packet which needs the pop processing removes one label from the head of the label stack. As the result of the pop processing, there are one case of returning to an IP packet and another case of remaining as an MPLS packet. The case of returning to an IP packet means that the LSR is the Egress Edge-LSR, and thereafter the above-mentioned IP routing processing is performed. In the case of remaining as the MPLS packet, it is necessary to do the label processing again by reference to the ILM and the NHLFE. This pop processing may be done several times in some cases. A system needs to cope with the repetition of this pop processing, which makes the system complicated and deteriorate in the performance. For example, in the method in which the next packet is not processed until the whole processing as for one packet is completed, if two pop processing is generated, a packet arriving at later may be delayed by one packet processing, compared with the case of not generating two pops. Therefore, when receiving a plurality of packets to be subjected to two and more pop processing, the number of the packets in the wait state is increased and there is a fear of falling into a situation of abandoning packets necessarily without processing.
As described in the above, the LSR needs not only an MPLS packet but also an IP packet processing including routing, and a method of integrating the both MPLS and IP processing for efficient and rapid processing is required.